package leetcode.code1191;

import java.math.BigInteger;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution3 implements IDebug {

	BigInteger mod = BigInteger.valueOf((int) 1e9 + 7);

	public int kConcatenationMaxSum(int[] arr, int k) {
		BigInteger[] max1 = this.max(arr, BigInteger.valueOf(0), BigInteger.valueOf(0), 0);
		if (k == 1) {//
			return max1[0].mod(mod).intValue();
		}
		BigInteger[] max2 = this.max(arr, max1[0], max1[1], arr[0]);
		// 增加一组最大值没有变大，那么增加多少个都无效
		if (max1[0] == max2[0] || k == 2) {// 就2个
			return max2[0].mod(mod).intValue();// 丢，这取max1[0]最后一个用例简直了
		}
		BigInteger[] max3 = this.max(arr, max2[0], max2[1], arr[0]);
		// 两组就能产生最大，max2结束
		if (max2[0] == max3[0]) {
			return max2[0].mod(mod).intValue();
		}
		// 每增加一组都能扩大最大值
		return max3[0].subtract(max2[0]).multiply(BigInteger.valueOf(k - 2)).add(max2[0]).mod(mod).intValue();
	}

	// arr，前一个数组最大子数组，前一个数组以最后一位结尾的最大子数组，最大值基础
	public BigInteger[] max(int[] arr, BigInteger preMax, BigInteger preMaxWithEnd, int basic) {
		BigInteger last = preMaxWithEnd.add(BigInteger.valueOf(arr[0])).max(BigInteger.valueOf(basic));
		BigInteger max = preMax.max(last);
		for (int i = 1; i < arr.length; i++) {
			BigInteger cur = BigInteger.valueOf(arr[i]);
			last = cur.max(last.add(cur));
			max = max.max(last);
		}
		return new BigInteger[] { max, last };// 这个mod
	}

	@Override
	public void debug4() {
//		System.out.println(1000000000 % mod);
//		System.out.println(1000000000 - 999999993);
		H.compare(1, this.kConcatenationMaxSum(H.str2array3("[1,-1]"), 1));
		H.compare(999999937, this.kConcatenationMaxSum(
				H.str2array3("[10000,10000,10000,10000,10000,10000,10000,10000,10000,10000]"), 100000));
		H.compare(4, this.kConcatenationMaxSum(H.str2array3("[4,-10,-2,-3,4]"), 1));
		H.compare(9, this.kConcatenationMaxSum(H.str2array3("[1,2]"), 3));
		H.compare(2, this.kConcatenationMaxSum(H.str2array3("[1,-2,1]"), 5));
		H.compare(0, this.kConcatenationMaxSum(H.str2array3("[-1,-2]"), 7));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
